perm filename AICONF.DOC[L70,TES] blob
sn#048919 filedate 1973-06-13 generic text, type T, neo UTF8
␈↓---------------------------------------------
␈↓* This␈α_work␈α↔was␈α_supported␈α↔(in␈α_part)␈α↔by␈α_Grant␈α_PHS␈α↔MH
06645-11␈α
from␈α∞the␈α
National␈α
Institute␈α∞of␈α
Mental␈α
Health,␈α∞and␈α
(in
part)␈α
by␈α the␈α
Advanced␈α Research␈α
Projects␈α Agency␈α
of␈α
the␈α Office
of␈α the␈α Secretary␈α of␈α Defense␈α (SD-183).
␈↓ The␈α⊂views␈α⊂and␈α⊂conclusions␈α⊂contained␈α⊂in␈α⊂this␈α⊂document␈α∂are
those␈α≠of␈α≠the␈α~authors␈α≠and␈α≠should␈α~not␈α≠be␈α≠interpreted␈α~as
necessarily␈α∞representing␈α∞the␈α∞official␈α∞policies,␈α∞either␈α
expressed
or␈α⊂implied,␈α∂of␈α⊂the␈α⊂Advanced␈α∂Research␈α⊂Projects␈α⊂Agency,␈α∂NIMH,
or␈α the␈α U.S.␈α Government.
---------------------------------------------
␈↓** Present␈α⊂affiliation:␈α⊂Xerox␈α⊂Corporation␈α⊂(Palo␈α⊂Alto␈α∂Research
Center).
␈↓␈↓ αw␈↓
Abstract␈↓
␈↓ LISP70␈α∂is␈α∞a␈α∂descendant␈α∞of␈α∂LISP␈α∞which␈α∂emphasizes␈α∞pattern-
directed␈α↔computation␈α↔and␈α_extensibility.␈α↔ A␈α↔function␈α_can␈α↔be
defined␈α⊃by␈α⊂a␈α⊃set␈α⊂of␈α⊃pattern␈α⊂rewrite␈α⊃rules␈α⊂as␈α⊃well␈α⊂as␈α⊃by␈α⊂the
normal␈α LAMBDA␈α method.␈α New␈α rewrite␈α rules␈α can␈α be␈α added␈α to␈α a
previously␈α⊂defined␈α⊂function;␈α⊂thus␈α⊂a␈α⊂LISP70␈α⊂function␈α⊂is␈α⊃said␈α⊂to
be␈α⊃"extensible".␈α⊃ It␈α⊂is␈α⊃possible␈α⊃to␈α⊂have␈α⊃new␈α⊃rules␈α⊃merged␈α⊂in
automatically␈α→such␈α→that␈α→special␈α→cases␈α→are␈α→checked␈α_before
general␈α∩cases.␈α∩ Some␈α⊃of␈α∩the␈α∩facilities␈α⊃of␈α∩the␈α∩rewrite␈α⊃system
are␈α described␈α and␈α a␈α variety␈α of␈α applications␈α are␈α demonstrated.
␈↓ αX␈↓
Background␈↓
␈↓ During␈α≤the␈α≠past␈α≤decade,␈α≠LISP␈↓↓19␈↓␈α≤has␈α≠been␈α≤a␈α≠principal
programming␈α≤language␈α≤for␈α≤artificial␈α≤intelligence␈α≤and␈α≤other
frontier␈α∃applications␈α∃of␈α∃computers.␈α∃ Like␈α∃other␈α⊗widely␈α∃used
languages,␈α⊃it␈α⊃has␈α⊃spawned␈α⊃many␈α⊃variants,␈α⊃each␈α∩attempting␈α⊃to
make␈α∃one␈α∀or␈α∃more␈α∃improvements.␈α∀ Among␈α∃the␈α∃aspects␈α∀that
have␈α∞received␈α∞particular␈α∞attention␈α∞are␈α∞notation,␈↓↓1,12,17,23␈↓␈α∞control
structure,␈↓↓5,14,20,22␈↓␈α≥data␈α≥base␈α≥management,␈↓↓15,20,25␈↓␈α≥interactive
editing␈α and␈α debugging,␈↓↓27␈↓␈α and␈α execution␈α efficiency.
A␈α∂need␈α∂for␈α∂a␈α∂successor␈α∂to␈α∂LISP␈α∂has␈α∂been␈α∂recognized,␈↓↓3␈↓␈α∞and
several␈α∞efforts␈α∞in␈α
this␈α∞direction␈α∞are␈α
under␈α∞way.␈α∞ The␈α
approach
being␈α∪taken␈α∀with␈α∪TENEX-LISP␈α∀is␈α∪to␈α∀begin␈α∪with␈α∀an␈α∪excellent
␈↓debugging␈α∞system␈↓↓26␈↓␈α∞and␈α∂to␈α∞add␈α∞on␈α∞flexible␈α∂control␈α∞structure.␈↓↓2␈↓
The␈α∂approach␈α∂taken␈α∂by␈α∂LISP70␈α∂and␈α∂by␈α∂ECL␈↓↓29␈↓␈α∂is␈α∂to␈α⊂begin␈α∂with
an␈α∞extensible␈α∞kernel␈α∞language␈α∂which␈α∞users␈α∞can␈α∞tailor␈α∂and␈α∞tune
to␈α their␈α own␈α needs.
"Tailoring"␈α∞a␈α∞language␈α∂means␈α∞defining␈α∞facilities␈α∂which␈α∞assist
in␈α
the␈α∞solution␈α
of␈α∞particular␈α
kinds␈α
of␈α∞problems␈α
which␈α∞may␈α
have
been␈α
unanticipated␈α∞by␈α
the␈α
designers␈α∞of␈α
the␈α
kernel.␈α∞ "Tuning"␈α
a
language␈α⊃means␈α⊃specifying␈α⊃more␈α⊃efficient␈α⊃implementations␈α⊃for
statements␈α∨which␈α∨are␈α∨executed␈α∨frequently␈α in␈α∨particular
programs.
A␈α⊂language␈α∂that␈α⊂can␈α∂be␈α⊂used␈α∂on␈α⊂only␈α∂one␈α⊂computer␈α⊂is␈α∂not
of␈α⊃universal␈α⊃utility;␈α⊃the␈α⊂ability␈α⊃to␈α⊃transfer␈α⊃programs␈α⊂between
computers␈α∩increases␈α∩its␈α∪value.␈α∩ However,␈α∩a␈α∩language␈α∪that␈α∩is
extensible␈α∞both␈α
upward␈α∞and␈α
downward␈α∞is␈α
difficult␈α∞to␈α
transport
if␈α4downward␈α3extensions␈α4mention␈α3machine-dependent
features.␈↓↓8,9␈↓ ␈α!This␈α!consideration␈α!suggests␈α!the␈α!use␈α"of␈α!a
machine-independent␈α∞low-level␈α∞language␈↓↓4␈↓␈α
in␈α∞terms␈α∞of␈α∞which␈α
to
describe␈α downward␈α extensions.
␈↓ ↓g␈↓
Capabilities of LISP70␈↓
␈↓ The␈α aim␈α of␈α LISP70␈α
is␈α to␈α provide␈α a␈α flexible␈α
and␈α parsimonious
programming␈α⊃medium␈α⊂for␈α⊃symbolic␈α⊂processing␈α⊃and␈α⊃an␈α⊂efficient
implementation␈α for␈α that␈α medium␈α on␈α several␈α machines.
The␈α∂semantics␈α∂of␈α∂the␈α∂LISP70␈α∂kernel␈α∂subsumes␈α∂LISP1.5␈α∂and
Algol-60␈α_semantics.␈α↔ The␈α_syntax␈α↔provides␈α_three␈α↔high-level
notations:␈α↔S-expressions,␈α↔Algol-like␈α↔MLISP␈α↔expressions,␈α↔and
pattern-directed␈α∞rewrite␈α
rules.␈α∞ The␈α
syntax␈α∞and␈α∞semantics␈α
can
both␈α→be␈α~extended␈α→as␈α→described␈α~later␈α→in␈α→this␈α~paper.␈α→ By
extension,␈α↔it␈α↔is␈α_feasible␈α↔to␈α↔incorporate␈α↔the␈α_capabilities␈α↔of
virtually␈α_any␈α↔other␈α_programming␈α↔language.␈α_ Of␈α_course,␈α↔one
would␈α⊗take␈α⊗advantage␈α⊗of␈α⊗the␈α⊗techniques␈α⊗developed␈α⊗by␈α∃its
previous␈α∪implementors;␈α∩LISP70␈α∪simply␈α∩provides␈α∪a␈α∩convenient
medium␈α for␈α doing␈α this.
To␈α⊃maximize␈α∩efficiency␈α⊃and␈α⊃to␈α∩eliminate␈α⊃the␈α∩possibility␈α⊃of
an␈α≠inconsistent␈α≠compiler␈α≠and␈α≠interpreter,␈α≠all␈α≤programs␈α≠in
LISP70␈α∀are␈α∀compiled.␈α∀ There␈α∃is␈α∀no␈α∀interpreter␈α∀in␈α∃the␈α∀usual
sense;␈α⊃the␈α⊂function␈α⊃EVAL␈α⊂compiles␈α⊃its␈α⊂argument␈α⊃with␈α⊂respect
to␈α∩the␈α∩current␈α∩environment␈α⊃and␈α∩then␈α∩executes␈α∩the␈α⊃machine-
language␈α∞code.␈α∞ To␈α∞extend␈α∞the␈α∞language,␈α∞extensions␈α∞need␈α∞only
be␈α made␈α to␈α the␈α compiler,␈α not␈α also␈α to␈α an␈α interpreter.
One␈α disadvantage␈α of␈α a␈α compiler␈α is␈α that␈α
certain␈α sophisticated
debugging␈α∂techniques␈α∂such␈α∞as␈α∂the␈α∂"BREAKIN"␈α∂of␈α∞TENEX-LISP␈↓↓26␈↓
are␈α≥more␈α≥difficult␈α≥to␈α≥implement␈α≥than␈α≥in␈α≥an␈α≥interpreter.
However,␈α∀we␈α∀feel␈α∀that␈α∀the␈α∀extra␈α∀effort␈α∀needed␈α∀for␈α∀this␈α∪is
worth␈α expending␈α to␈α retain␈α the␈α advantages␈α of␈α a␈α compiler.
LISP70␈α⊃generates␈α⊃code␈α⊃for␈α⊃an␈α⊃"ideal␈α⊃LISP␈α∩machine"␈α⊃called
"ML"␈α↔and␈α↔only␈α↔the␈α↔translation␈α↔from␈α↔ML␈α↔to␈α↔object␈α⊗machine
language␈α∪is␈α∪machine-dependent.␈α∪ Thus,␈α∀downward␈α∪extensions
can␈α∩be␈α∩factored␈α∪into␈α∩a␈α∩machine-independent␈α∩and␈α∪a␈α∩machine-
dependent␈α∃part,␈α∃and␈α⊗during␈α∃program␈α∃transfer,␈α⊗the␈α∃machine-
dependent␈α⊂recoding␈α⊂(if␈α⊂any)␈α⊂is␈α⊂clearly␈α⊂isolated.␈α⊂ An␈α⊂execution
image␈α∃on␈α∃one␈α∃computer␈α⊗could␈α∃be␈α∃transliterated␈α∃to␈α⊗ML␈α∃and
␈↓transported␈α∩to␈α⊃a␈α∩different␈α∩machine.␈α⊃ This␈α∩capability␈α∩could␈α⊃be
used␈α∪to␈α∀transport␈α∪programs␈α∀around␈α∪computer␈α∀networks,␈α∪and
for␈α bootstrapping␈α of␈α the␈α compiler␈α itself.
In␈α∩order␈α∩to␈α∩execute␈α∩the␈α∩EVAL␈α∩function,␈α∩the␈α∪compiler␈α∩and
parts␈α⊂of␈α⊃the␈α⊂symbol␈α⊃table␈α⊂must␈α⊃be␈α⊂present␈α⊃during␈α⊂execution.
This␈α⊃requirement␈α⊃and␈α∩the␈α⊃goal␈α⊃of␈α∩extensibility␈α⊃are␈α⊃met␈α∩by␈α⊃a
pattern-directed␈α→translator␈α→whose␈α→rules␈α→are␈α→compiled␈α_into
dense␈α∂and␈α∂efficient␈α∂code.␈α∂ The␈α∂same␈α∂pattern␈α∂matcher␈α∂as␈α∂used
in␈α∂the␈α∂translator␈α∂also␈α∂is␈α∂available␈α∂for␈α⊂goal-directed␈α∂procedure
invocation␈α in␈α A.I.␈α programs.
Among␈α the␈α specific␈α improvements␈α LISP70␈α makes␈α to␈α LISP␈α are
backtrack␈α and␈α coroutine␈α control␈α structure,␈α
streaming,␈α long-term
memory␈α∃for␈α∃large␈α∀data␈α∃bases,␈α∃data␈α∃typing,␈α∀pattern-directed
computation,␈α→and␈α→extensible␈α→functions.␈α→ The␈α_implementation
provides␈α/dynamic␈α.storage␈α/allocation,␈α/relocation,␈α.and
segmentation.
The␈α⊗subjects␈α⊗to␈α⊗be␈α⊗covered␈α⊗in␈α⊗the␈α⊗present␈α↔paper␈α⊗are
pattern-directed␈α computation␈α and␈α extensible␈α functions.
␈↓ ↓%␈↓
Pattern Directed Computation␈↓
␈↓␈↓
Rewrite Rules ␈↓
␈↓ Many␈α∨of␈α∨the␈α∨data␈α∨tranformations␈α∨performed␈α in␈α∨LISP
applications␈α∃are␈α∀more␈α∃easily␈α∀described␈α∃by␈α∃pattern␈α∀matching
rules␈α~than␈α~by␈α~algorithms.␈↓↓11,13,15,20,25,28␈↓ ␈α~In␈α~addition,␈α~pattern
matching␈α∩rules␈α∩are␈α∪appropriate␈α∩for␈α∩the␈α∩description␈α∪of␈α∩input-
output␈α↔conversion,␈α↔parsing,␈α↔and␈α↔compiling.␈↓↓24␈↓ ␈α_LISP70␈α↔places
great␈α≡emphasis␈α≡on␈α≡"pattern␈α≡rewrite␈α≡rules"␈↓↓6,7,16,30␈↓␈α≡as␈α≡an
alternative␈α∩and␈α⊃adjunct␈α∩to␈α⊃algorithms␈α∩as␈α⊃a␈α∩means␈α∩of␈α⊃defining
functions.
␈↓ A␈α∩brief␈α⊃explanation␈α∩of␈α⊃rewrite␈α∩rule␈α⊃syntax␈α∩and␈α⊃semantics
will␈α∀be␈α∀presented␈α∃with␈α∀some␈α∀examples␈α∀to␈α∃demonstrate␈α∀the
clarity␈α of␈α the␈α notation.
Each␈α∞rule␈α
is␈α∞of␈α
the␈α∞form␈α
DEC→REC.␈α∞ The␈α∞DEC␈α
(decomposer)
is␈α∂matched␈α∞against␈α∂the␈α∂"input␈α∞stream".␈α∂ If␈α∞it␈α∂matches,␈α∂then␈α∞the
REC␈α (recomposer)␈α generates␈α the␈α "output␈α stream".
A␈α∩literal␈α∩in␈α∩a␈α∩pattern␈α∩is␈α∩represented␈α∩by␈α∩itself␈α∩if␈α∩it␈α∩is␈α⊃an
identifier␈α∀or␈α∀number,␈α∪or␈α∀preceded␈α∀by␈α∪a␈α∀quote␈α∀(')␈α∪if␈α∀it␈α∀is␈α∪a
special␈α character.
␈↓∞ RULES OF SQUARE =
2 → 4,
5 → 25,
12 → 144 ;
␈↓ A␈α→private␈α~variable␈α→of␈α~the␈α→rule␈α~is␈α→represented␈α~by␈α→an
identifier␈α∞prefixed␈α∞by␈α∞a␈α∞colon␈α∞(:);␈α
it␈α∞may␈α∞be␈α∞bound␈α∞to␈α∞only␈α
one
value␈α during␈α operation␈α of␈α the␈α rule.
␈↓∞ RULES OF EQUAL =
:X :X → T,
:X :Y → NIL ;
␈↓ A␈α∞list␈α∞is␈α∞represented␈α∞by␈α∞a␈α∞pair␈α∞of␈α∂parentheses␈α∞surrounding
␈↓the␈α∪representations␈α∪of␈α∪its␈α∪elements.␈α∪ A␈α∪segment␈α∪of␈α∪zero␈α∪or
more␈α elements␈α is␈α represented␈α by␈α an␈α ellipsis␈α symbol␈α (...).
␈↓∞ RULES OF CAR =
(:X ...) → :X ;
␈↓∞ RULES OF CDR =
(:X ...) → (...) ;
␈↓∞ RULES OF CONS =
:X (...) → (:X ...) ;
␈↓∞ RULES OF ATOM =
(:X ...) → NIL,
:X → T ;
␈↓∞ RULES OF APPEND =
(...) (...) → (... ...) ;
␈↓ If␈α→a␈α_segment␈α→needs␈α→a␈α_name,␈α→it␈α_is␈α→represented␈α→by␈α_an
identifier␈α prefixed␈α by␈α a␈α double-colon␈α (::).
␈↓∞ RULES OF ASSOC =
:X (... (:X ::Y) ...) → (:X ::Y),
:X (...) → NIL ;
␈↓ A␈α↔function␈α↔F(X,Y,Z)␈α↔can␈α↔be␈α↔called␈α↔in␈α↔a␈α↔pattern␈α↔by␈α↔the
construct:␈α <F :X :Y :Z>.
␈↓∞ RULES OF LENGTH =
( ) → 0,
(:X ...) → <ADD1 <LENGTH (...)>> ;
␈↓ The␈α≤facilities␈α≠described␈α≤so␈α≤far␈α≠are␈α≤standard␈α≤in␈α≠most
pattern-directed␈α languages.
␈↓
List Structure Transformations ␈↓
␈↓ The␈α∞following␈α∞set␈α∞of␈α∞rules␈α∞defines␈α∞a␈α∂function␈α∞MOVE_BLOCK
of␈α three␈α arguments:␈α a␈α block␈α to␈α be␈α moved,␈α a␈α location␈α to␈α which␈α it
should␈α⊂be␈α⊂moved,␈α⊂and␈α⊃a␈α⊂representation␈α⊂of␈α⊂the␈α⊃current␈α⊂world.
The␈α⊃function␈α⊃moves␈α⊃block␈α∩:B␈α⊃from␈α⊃its␈α⊃current␈α⊃location␈α∩in␈α⊃the
world␈α⊃to␈α⊃location␈α⊃:TO,␈α⊃and␈α⊃the␈α⊃transformed␈α⊃representation␈α⊃of
the␈α world␈α is␈α returned.
␈↓∞ RULES OF MOVE_BLOCK =
:B :TO (... (:TO ... :B ...) ...)
→ (... (:TO ... :B ...) ...),
:B :TO (... (... :B ...) ... (:TO ... ) ...)
→ (... (... ...) ... (:TO ... :B) ...),
:B :TO (... (:TO ... ) ... (... :B ...) ...)
→ (... (:TO ... :B) ... (... ...) ...),
:B :TO (... (... :B ...) ...)
→ (... (... ...) ... (:TO :B)),
:B :TO (...)
␈↓∞ → <ERROR (BLOCK :B NOT IN (...))> ;
␈↓In␈α∞the␈α
first␈α∞case,␈α
the␈α∞block␈α
is␈α∞already␈α
where␈α∞it␈α
belongs,␈α∞so␈α
the
world␈α⊂does␈α⊂not␈α⊂change;␈α⊂in␈α⊂the␈α⊂second,␈α⊂the␈α⊂block␈α⊂is␈α⊂moved␈α⊂to
the␈α⊃right;␈α⊃in␈α⊃the␈α⊃third,␈α⊃to␈α⊂the␈α⊃left;␈α⊃in␈α⊃the␈α⊃fourth,␈α⊃the␈α⊂location
:TO␈α⊂does␈α⊂not␈α∂exist␈α⊂yet␈α⊂and␈α∂is␈α⊂created;␈α⊂in␈α∂the␈α⊂last␈α⊂case,␈α⊂:B␈α∂is
not␈α in␈α the␈α world␈α and␈α the␈α ERROR␈α routine␈α is␈α called.
Functions␈α_such␈α_as␈α→MOVE_BLOCK␈α_have␈α_been␈α_used␈α→in␈α_a
simple␈α≠planning␈α≠program␈α≠written␈α≠by␈α≠one␈α≠of␈α≠the␈α~authors.
Imagine␈α
writing␈α
MOVE_BLOCK␈α
as␈α
an␈α
algorithm;␈α
it␈α∞would␈α
require
the␈α→use␈α→of␈α~auxiliary␈α→functions␈α→or␈α~of␈α→a␈α→PROG␈α~with␈α→state
variables␈α~and␈α~loops.␈α~ Bugs␈α~would␈α~be␈α~more␈α~likely␈α≠in␈α~the
algorithm␈α because␈α its␈α operation␈α would␈α not␈α be␈α so␈α lucid.
␈↓
Replacement ␈↓
␈↓ A␈α∂function␈α∂call␈α∂in␈α⊂a␈α∂DEC␈α∂pattern␈α∂is␈α∂called␈α⊂a␈α∂"replacement".
A␈α→replacement␈α_has␈α→two␈α→interesting␈α_aspects.␈α→ First,␈α→if␈α_the
function␈α requires␈α more␈α
arguments␈α than␈α it␈α
is␈α passed,␈α it␈α
will␈α take
additional␈α≥arguments␈α≤off␈α≥the␈α≤front␈α≥of␈α≤the␈α≥input␈α≤stream.
Furthermore,␈α!the␈α!value␈α!returned␈α!by␈α!a␈α!replacement␈α!is
appended␈α≤to␈α≤the␈α≠front␈α≤of␈α≤the␈α≠input␈α≤stream.␈α≤ Thus,␈α≠the
replacement␈α
<F>␈α
behaves␈α
like␈α
a␈α
non-terminal␈α
symbol␈α
of␈α
a␈α top-
down␈α∂parser.␈α∞ In␈α∂effect,␈α∂the␈α∞function␈α∂F␈α∞is␈α∂invoked␈α∂to␈α∞translate
a␈α→substream␈α→of␈α→the␈α→input␈α→stream,␈α→and␈α→that␈α→substream␈α→is
replaced␈α
by␈α
its␈α
translation.␈α∞ The␈α
altered␈α
input␈α
stream␈α∞can␈α
then
continue␈α to␈α be␈α matched␈α by␈α the␈α pattern␈α to␈α the␈α right␈α of␈α <F>.
␈↓ The␈α∩following␈α⊃example␈α∩is␈α∩from␈α⊃the␈α∩MLISP␈α∩compiler,␈α⊃which
calls␈α⊂itself␈α⊃recursively␈α⊂to␈α⊂translate␈α⊃the␈α⊂condition␈α⊂and␈α⊃arms␈α⊂of
an␈α IF-statement␈α to␈α LISP:
␈↓∞ RULES OF MLISP =
IF <MLISP>:X THEN <MLISP>:Y ELSE <MLISP>:Z
→ (COND (:X :Y) (T :Z)),
IF <MLISP>:X THEN <MLISP>:Y
→ (COND (:X :Y) (T NIL)),
IF <MLISP>:X
→ <ERROR (MISSING THEN)>,
IF → <ERROR (ILLEGAL EXPRESSION AFTER IF)>;
␈↓ Here␈α∪is␈α∪another␈α∩example.␈α∪ The␈α∪predicate␈α∪PALINDROME␈α∩is
␈↓true␈α∞iff␈α∞the␈α∞input␈α∞stream␈α∞is␈α∞a␈α∞mirror␈α∞image␈α∞of␈α∞itself,␈α∞i.e.,␈α∞if␈α∞the
left␈α_and␈α_right␈α_ends␈α_are␈α↔equal␈α_and␈α_the␈α_middle␈α_is␈α_itself␈α↔a
palindrome.
␈↓∞ RULES OF PALINDROME = :X → T,
:X :X → T,
:X <PALINDROME>T :X → T,
... → NIL;
␈↓␈↓ α␈↓
Extensible Functions␈↓
␈↓ New␈α∀rules␈α∀may␈α∀be␈α∀added␈α∀to␈α∀an␈α∀existing␈α∀set␈α∃of␈α∀rewrite
rules␈α⊃under␈α⊃program␈α⊃control;␈α⊃thus,␈α⊃any␈α⊃compiler␈α⊃table␈α⊃or␈α⊂any
other␈α⊂system␈α⊂of␈α⊂rewrite␈α⊃rules␈α⊂can␈α⊂be␈α⊂extended␈α⊂by␈α⊃the␈α⊂user.
For␈α⊗this␈α↔reason,␈α⊗a␈α⊗set␈α↔of␈α⊗rewrite␈α⊗rules␈α↔is␈α⊗said␈α⊗to␈α↔be␈α⊗an
"extensible␈α
function".␈α
The␈α
"ALSO"␈α clause␈α
is␈α
used␈α
to␈α
add␈α cases
to␈α an␈α extensible␈α function:
␈↓∞ RULES OF MLISP ALSO =
IF <MLISP>:X THEN <MLISP>:Y ELSE
→ <ERROR (MISSING EXPRESSION AFTER ELSE)>,
IF <MLISP>:X THEN
→ <ERROR (MISSING EXPRESSION AFTER THEN)>;
␈↓ Extensions␈α⊂can␈α⊂be␈α∂made␈α⊂effective␈α⊂throughout␈α⊂the␈α∂program
or␈α only␈α in␈α the␈α current␈α block,␈α as␈α the␈α user␈α wishes.
A␈α↔regular␈α⊗LAMBDA␈α↔function␈α↔can␈α⊗also␈α↔be␈α↔extended.␈α⊗ Its
bound␈α∪variables␈α∪are␈α∪considered␈α∪analogous␈α∪to␈α∪a␈α∪DEC␈α∪and␈α∪its
body␈α⊂analogous␈α∂to␈α⊂a␈α∂REC.␈α⊂ Accordingly,␈α∂the␈α⊂compiler␈α∂converts
it␈α~to␈α~an␈α~equivalent␈α~rewrite␈α~function␈α~of␈α~one␈α~rule␈α→before
extending␈α it.
␈↓
The Extensible Compiler ␈↓
␈↓ To␈α⊂make␈α⊂an␈α⊃extensible␈α⊂compiler␈α⊂practical,␈α⊂the␈α⊃casual␈α⊂user
must␈α be␈α able␈α to␈α understand␈α how␈α it␈α works␈α in␈α order␈α to␈α change␈α it.
We␈α⊂have␈α⊂found␈α⊂this␈α⊂to␈α⊂be␈α⊂no␈α⊂problem␈α⊂with␈α⊂users␈α⊂of␈α∂MLISP2,
the␈α∂predecessor␈α⊂to␈α∂LISP70.␈α∂ Its␈α⊂extensible␈α∂compiler␈α⊂has␈α∂been
used␈α⊃to␈α⊃write␈α⊃parsers␈α⊃quickly␈α⊃by␈α⊃A.I.␈α∩researchers␈α⊃previously
unfamiliar␈α with␈α parsing␈α techniques.
␈↓ To␈α~demonstrate␈α→that␈α~it␈α~is␈α→not␈α~inordinately␈α~difficult␈α→to
understand␈α≡the␈α≡LISP70␈α≡compiler,␈α≡those␈α≡rules␈α≡which␈α≥get
involved␈α∪in␈α∩translating␈α∪a␈α∩particular␈α∪statement␈α∩from␈α∪MLISP␈α∩to
LAP/PDP-10␈α∂are␈α∞shown␈α∂below.␈α∞ A␈α∂simplified␈α∂LISP70␈α∞(typeless
and␈α∞unhierarchical)␈α∞is␈α∞used␈α∞in␈α∞the␈α∞examples,␈α∞but␈α∞the␈α∞real␈α∞thing
is␈α not␈α much␈α more␈α complicated.
The␈α statement␈α to␈α be␈α translated␈α is:
␈↓∞ IF A < B THEN C ELSE D
␈↓The␈α rules␈α invoked␈α in␈α the␈α MLISP-to-LISP␈α translator␈α are:
␈↓∞ RULES OF MLISP =
IF <MLISP>:X THEN <MLISP>:Y ELSE <MLISP>:Z
→ (COND (:X :Y) (T :Z)),
:X '< :Y
→ (LESSP :X :Y),
:VAR → :VAR ;
␈↓The␈α LISP␈α translation␈α is␈α thus:
␈↓∞ (COND ((LESSP A B) C) (T D))
␈↓ The␈α≤LISP-to-ML␈α≥compiler␈α≤below␈α≤utilizes␈α≥the␈α≤following
feature:␈α⊃if␈α⊃a␈α⊃colon␈α⊃variable␈α⊃occurs␈α⊃in␈α⊃the␈α⊃REC␈α⊃but␈α⊃it␈α⊃did␈α⊂not
occur␈α∩in␈α∩the␈α∩DEC,␈α∩an␈α∩"existential␈α∩value"␈α∩(which␈α∩is␈α⊃something
like␈α∂a␈α∂generated␈α∞symbol)␈α∂is␈α∂bound␈α∞to␈α∂it.␈α∂ Here,␈α∂the␈α∞existential
value␈α is␈α used␈α as␈α a␈α compiler-generated␈α label.
The␈α∂language␈α∂ML␈α∂is␈α⊂based␈α∂on␈α∂the␈α∂machine␈α∂language␈α⊂of␈α∂the
Burroughs␈α∪5000␈α∪and␈α∪its␈α∪descendants.␈α∪ For␈α∪example,␈α∀the␈α∪ML
operator␈α→"DJUMPF"␈α_means␈α→"destructive␈α_jump␈α→if␈α→false".␈α_ It
jumps␈α only␈α
if␈α the␈α top␈α
of␈α the␈α
stack␈α is␈α false␈α
but␈α always␈α
pops␈α the
stack.
␈↓∞ RULES OF COMPILE =
(COND (T :E))
→ <COMPILE :E>,
(COND (:B :E) ...)
→ <COMPILE :B>
(DJUMPF :ELSE)
<COMPILE :E>
(JUMP :OUT)
(LABEL :ELSE)
<COMPILE (COND ...)>
(LABEL :OUT),
(LESSP :A :B)
→ <COMPILE :A>
<COMPILE :B>
(FETCH (FUNCTION LESSP)),
:V → (FETCH (VARIABLE :V)) ;
␈↓ The␈α∞unoptimized␈α∞ML-to-LAP␈α∞translator␈α∞below␈α∂assumes␈α∞that
the␈α∂stack␈α∂of␈α∂the␈α∂ideal␈α∂machine␈α∂is␈α∂represented␈α∂on␈α∂the␈α∞PDP-10
by␈α∞a␈α∞single␈α∂stack␈α∞based␈α∞on␈α∞register␈α∂"P",␈α∞that␈α∞there␈α∞is␈α∂a␈α∞single
working␈α∪register␈α∪"VAL",␈α∪and␈α∪that␈α∪variables␈α∪can␈α∪be␈α∩accessed
from␈α∞fixed␈α
locations␈α∞in␈α∞memory.␈α
(None␈α∞of␈α∞this␈α
is␈α∞really␈α∞true␈α
in
the␈α actual␈α implementation.)
␈↓∞ RULES OF ML =
(DJUMPF :LBL)
→ (POP P VAL)
(JUMPE VAL :LBL),
(JUMP :LBL)
␈↓∞ → (JUMPA VAL :LBL),
(LABEL :LBL)
→ :LBL,
(FETCH (FUNCTION LESSP))
→ (POP P VAL)
(CAMG VAL 0 P)
(SKIPA VAL NIL)
(MOVEI VAL T)
(MOVEM VAL 0 P),
(FETCH (VARIABLE :V))
→ (PUSH P :V) ;
␈↓ The␈α code␈α generated␈α is␈α thus:
␈↓∞ ML LAP
(FETCH (VARIABLE A)) (PUSH P A)
(FETCH (VARIABLE B)) (PUSH P B)
(FETCH (FUNCTION LESSP)) (POP P VAL)
(CAMG VAL 0 P)
(SKIPA VAL ZERO)
(MOVEI VAL 1)
(MOVEM VAL 0 P)
(DJUMPF E0001) (POP P VAL)
(JUMPE VAL E0001)
(FETCH (VARIABLE C)) (PUSH P C)
(JUMP E0002) (JUMPA VAL E0002)
(LABEL E0001) E0001
(FETCH (VARIABLE D)) (PUSH P D)
(LABEL E0002) E0002
␈↓In␈α∞the␈α
actual␈α∞compiler,␈α∞special␈α
rules␈α∞for␈α∞optimizing␈α
conditionals,
a␈α∂peephole␈α∂optimizer,␈α∂and␈α∂additional␈α∂working␈α∂registers␈α∂reduce
this␈α to␈α six␈α instructions.
␈↓ P␈↓
Automatic Ordering Of Rewrite Rules␈↓
␈↓ In␈α⊃most␈α⊃pattern␈α⊃matchers,␈α⊃candidate␈α⊃patterns␈α⊃to␈α⊃match␈α⊃an
input␈α∞stream␈α∂are␈α∞tried␈α∞either␈α∂in␈α∞order␈α∞of␈α∂appearance␈α∞on␈α∂a␈α∞list
or␈α≥in␈α≡an␈α≥essentially␈α≡random␈α≥order␈α≡not␈α≥obvious␈α≡to␈α≥the
programmer.␈α
LISP70␈α
tries␈α
matches␈α in␈α
an␈α
order␈α
specified␈α
by␈α an
"ordering␈α function"␈α associated␈α with␈α each␈α set␈α of␈α rewrite␈α rules.
One␈α≠common␈α≠ordering␈α~is␈α≠"BY␈α≠APPEARANCE",␈α≠which␈α~is
appropriate␈α⊂when␈α∂the␈α⊂programmer␈α∂wants␈α⊂conscious␈α⊂control␈α∂of
the␈α∂ordering.␈α∂ Another␈α∂is␈α∂"BY␈α∂SPECIFICITY",␈α∂which␈α∂is␈α⊂useful␈α∂in
left-to-right␈α"parsers␈α!and␈α"other␈α!applications␈α"where␈α!the
compiler␈α⊗can␈α⊗be␈α⊗trusted␈α↔to␈α⊗order␈α⊗the␈α⊗rules␈α⊗so␈α↔that␈α⊗more
specific␈α⊗cases␈α∃are␈α⊗tried␈α⊗before␈α∃more␈α⊗general␈α⊗ones.␈α∃ When
neither␈α≡of␈α≡these␈α∨standard␈α≡functions␈α≡is␈α∨appropriate,␈α≡the
␈↓programmer␈α∞can␈α∞define␈α∂and␈α∞use␈α∞specialized␈α∂ordering␈α∞functions,
or␈α can␈α extend␈α SPECIFICITY␈α to␈α meet␈α the␈α special␈α requirements.
Automatic␈α≤ordering␈α≥is␈α≤convenient␈α≤for␈α≥a␈α≤user␈α≥who␈α≤is
extending␈α≥a␈α≥compiler,␈α≥a␈α≥natural␈α≥language␈α≥parser,␈α≥or␈α≤an
inference␈α⊗system.␈α⊗ It␈α⊗can␈α⊗eliminate␈α⊗the␈α⊗need␈α⊗to␈α↔study␈α⊗the
existing␈α∩rules␈α∩simply␈α∩to␈α∪determine␈α∩where␈α∩to␈α∩position␈α∪a␈α∩new
rule.␈α~ Ordering␈α→functions␈α~can␈α→also␈α~be␈α→designed␈α~to␈α→detect
inconsistencies␈α⊃and␈α∩ambiguities␈α⊃and␈α⊃to␈α∩discover␈α⊃opportunities
for␈α generalization␈α of␈α similar␈α rules.
As␈α
an␈α∞example,␈α
take␈α∞the␈α
LISP-TO-ML␈α∞translator␈α
"COMPILE",
which␈α↔includes␈α⊗the␈α↔following␈α⊗rule␈α↔for␈α⊗the␈α↔intrinsic␈α⊗function
PLUS␈α (slightly␈α simplified␈α for␈α presentation):
␈↓∞ RULES OF COMPILE =
(PLUS :X :Y)
→ <COMPILE :X>
<COMPILE :Y>
(FETCH (FUNCTION PLUS)) ;
␈↓ To␈α
add␈α
special␈α
cases␈α
to␈α the␈α
compiler␈α
for␈α
sums␈α
including␈α the
constant␈α∞zero,␈α∞the␈α∞user␈α∞could␈α∞include␈α∞the␈α∂following␈α∞declaration
in␈α a␈α program:
␈↓∞ RULES OF COMPILE ALSO =
(PLUS :X 0) → <COMPILE :X>,
(PLUS 0 :X) → <COMPILE :X> ;
␈↓ The␈α∂compiler␈α∞is␈α∂ordered␈α∞by␈α∂SPECIFICITY,␈α∞which␈α∂knows␈α∞that
the␈α↔literal␈α↔␈↓∞0␈↓␈α↔is␈α↔more␈α↔specific␈α↔than␈α↔the␈α↔variable␈α↔:X␈α↔or␈α↔:Y.
Therefore,␈α both␈α of␈α the␈α new␈α rules␈α would␈α be␈α ordered␈α
before␈α the
original␈α⊗PLUS␈α∃rule.␈α⊗ Suppose␈α⊗the␈α∃added␈α⊗rules␈α⊗were␈α∃placed
after␈α⊃the␈α⊃general␈α∩rule;␈α⊃then␈α⊃the␈α∩original␈α⊃rule␈α⊃would␈α∩get␈α⊃first
crack␈α
at␈α
every␈α
input␈α
stream,␈α
and␈α
sums␈α
with␈α
zero␈α
would␈α
not␈α be
processed␈α as␈α special␈α cases.
␈↓
An Ordering Function ␈↓
␈↓ The␈α)complete␈α)definition␈α)of␈α)the␈α*ordering␈α)function
SPECIFICITY␈α⊗is␈α⊗beyond␈α⊗the␈α⊗scope␈α⊗of␈α⊗this␈α⊗paper.␈α↔ It␈α⊗works
roughly␈α
as␈α
follows.␈α∞ Comparing␈α
DEC␈α
patterns␈α
by␈α∞a␈α
left-to-right
scan,␈α⊃it␈α∩considers␈α⊃literals␈α∩more␈α⊃specific␈α∩than␈α⊃variables␈α∩and␈α⊃a
colon␈α
variable␈α
at␈α
its␈α
second␈α
occurrence␈α
more␈α
specific␈α
than␈α one
at␈α its␈α first␈α occurrence.␈α
The␈α specificity␈α of␈α a␈α replacement␈α
<F>␈α is
that␈α of␈α the␈α most␈α general␈α rule␈α in␈α the␈α function␈α F.
␈↓ A␈α∞DEC␈α∂with␈α∞an␈α∂ellipsis␈α∞is␈α∞considered␈α∂to␈α∞expand␈α∂to␈α∞multiple
rules␈α∃in␈α∃which␈α∃the␈α∃ellipsis␈α∃is␈α∀replaced␈α∃by␈α∃0,␈α∃1,␈α∃2,␈α∃3,␈α∃...␈α∀␈↓∞∞␈↓
consecutive␈α⊂variables.␈α∂ The␈α⊂specificity␈α∂of␈α⊂each␈α⊂expanded␈α∂rule
is␈α#considered␈α#separately.␈α# Observe␈α#that␈α#between␈α#two
expansions␈α↔of␈α↔an␈α⊗elliptic␈α↔rule␈α↔some␈α⊗other␈α↔rewrite␈α↔rule␈α⊗of
intermediate␈α specificity␈α may␈α lie.␈α Example:
␈↓∞ RULES OF SILLY =
A ... B ... C → 1,
A B :X :Y → 2;
␈↓Two␈α of␈α the␈α expansions␈α of␈α the␈α first␈α rule␈α are:
␈↓∞ A B :X C → 1,
A :Z B C → 1,
␈↓and␈α≠the␈α≠second␈α≠rule␈α≠of␈α≠SILLY␈α≠comes␈α≠between␈α≠these␈α≠in
specificity.
SPECIFICITY␈α∞is␈α∞itself␈α∞defined␈α∂by␈α∞a␈α∞system␈α∞of␈α∂rewrite␈α∞rules.
To␈α_give␈α_a␈α_flavor␈α_of␈α→how␈α_this␈α_is␈α_done,␈α_a␈α→very␈α_simplified
SPECIFICITY␈α∃will␈α∃be␈α∃defined.␈α∀ It␈α∃takes␈α∃two␈α∃arguments␈α∀(DEC
patterns␈α⊂translated␈α⊂to␈α⊂LISP␈α⊂notation)␈α⊂and␈α⊂returns␈α⊂them␈α⊂in␈α∂the
proper␈α order.
␈↓∞ RULES OF SPECIFICITY =
(COLON :V) (LITERAL :L)
→ (ORDER (LITERAL :L) (COLON :V)),
(LITERAL :L) (COLON :V)
→ (ORDER (LITERAL :L) (COLON :V)) ;
␈↓␈↓ ↓␈␈↓
Additional Facilities␈↓
␈↓ The␈α∩programmer␈α∪can␈α∩specify␈α∪either␈α∩deterministic␈α∪or␈α∩non-
deterministic␈α∞matching;␈α∂the␈α∞former␈α∂case␈α∞generates␈α∂faster␈α∞code
while␈α⊂the␈α∂latter␈α⊂provides␈α⊂for␈α∂backtracking.␈α⊂ Other␈α⊂facilities␈α∂of
the␈α∞rewrite␈α∂system␈α∞include␈α∞side-conditions,␈α∂conjunctive␈α∞match,
disjunctive␈α match,␈α non-match,␈α repetition,␈α evaluation␈α of␈α LISP␈α and
MLISP␈α↔expressions,␈α↔look-ahead,␈α↔look-behind,␈α↔and␈α↔reversible
rules.
DEC␈α∃patterns␈α∀can␈α∃be␈α∀used␈α∃outside␈α∀of␈α∃rewrite␈α∃rules␈α∀for
decomposition␈α of␈α data␈α structures␈α in␈α MLISP␈α statements.
␈↓ αQ␈↓
Applications␈↓
␈↓ It␈α~is␈α→easy␈α~to␈α~define␈α→a␈α~system␈α→of␈α~inference␈α~rules,␈α→of
assertions,␈α∂or␈α∞of␈α∂beliefs␈α∂as␈α∞a␈α∂rewrite␈α∂function.␈α∞ From␈α∂a␈α∂set␈α∞of
rules␈α∞can␈α∞be␈α∞retrieved␈α∞either␈α
all␈α∞of␈α∞the␈α∞assertions␈α∞or␈α∞the␈α
first
that␈α≠match␈α≠a␈α≠given␈α≤pattern.␈α≠ A␈α≠robot␈α≠planner␈α≤could␈α≠be
organized␈α8into␈α9RULES␈α8OF␈α8PHYSICS,␈α9RULES␈α8OF
INITIAL_CONDITIONS,␈α'RULES␈α'OF␈α'INFERENCE,␈α'RULES␈α'OF
STRATEGY,␈α∞etc.␈α∞ Note␈α∞that␈α∞goal-directed␈α∞procedure␈α∞invocation
is␈α⊂performed␈α⊂within␈α⊂each␈α⊂of␈α⊂these␈α⊂functions␈α⊃separately.␈α⊂ This
allows␈α∀for␈α∀segmentation␈α∀of␈α∀large␈α∀programs.␈α∃ Furthermore,␈α∀it
averts␈α
the␈α∞need␈α
to␈α∞rummage␈α
around␈α∞a␈α
conglomerate␈α∞data␈α
base
of␈α unrelated␈α rules.
Rewrite␈α≠rules␈α≠are␈α≠a␈α≠useful␈α≠tool␈α≠for␈α≠natural␈α~language
analysis,␈α↔whether␈α↔the␈α↔methods␈α↔used␈α↔are␈α↔based␈α_on␈α↔phrase
structure␈α⊃grammar,␈α⊃features,␈α⊃keywords,␈α⊃or␈α⊃word␈α⊃patterns.␈α⊃ A
use␈α→of␈α_LISP70␈α→with␈α_the␈α→latter␈α_method␈α→is␈α_described␈α→in␈α_a
companion␈α∪paper.␈↓↓10␈↓ ␈α∀ The␈α∪program␈α∪described␈α∀therein␈α∪utilizes
the␈α replacement␈α facility␈α extensively.
␈↓␈↓ ↑␈↓
Implementation of Rewrite Functions␈↓
␈↓ In␈α∪the␈α∩initial␈α∪implementation␈α∩of␈α∪LISP70,␈α∩rewrite␈α∪rules␈α∩are
processed␈α∃in␈α∃a␈α⊗top-down,␈α∃left-to-right␈α∃manner.␈α⊗ During␈α∃the
ordering␈α↔phase,␈α↔the␈α_rules␈α↔of␈α↔each␈α↔extensible␈α_function␈α↔are
factored␈α∂from␈α∂the␈α∞left␈α∂to␈α∂avoid␈α∞repetition␈α∂of␈α∂identical␈α∂tests␈α∞in
identical␈α∂circumstances.␈α∂ The␈α∞resulting␈α∂code␈α∂is␈α∂a␈α∞discrimination
tree␈α that␈α eliminates␈α many␈α choice-points␈α for␈α backtracking.
The␈α∞backtracking␈α∞implementation␈α∞is␈α∞an␈α∞improvement␈α∞of␈α∞that
developed␈α∩for␈α∩MLISP2.␈↓↓22␈↓ ␈α∪ It␈α∩incurs␈α∩little␈α∩overhead␈α∪of␈α∩either
time␈α or␈α space.
The␈α⊗machine␈α⊗code␈α↔generated␈α⊗for␈α⊗rewrite␈α↔rules␈α⊗consists
primarily␈α∃of␈α∃calls␈α∃on␈α∃scanning␈α∃and␈α∃testing␈α⊗functions.␈α∃ These
functions␈α∀are␈α∃generic␈α∀and␈α∃will␈α∀process␈α∃input␈α∀and␈α∃output␈α∀of
streams␈α
of␈α any␈α
type,␈α including␈α
lists,␈α character␈α
strings,␈α
files,␈α and
coroutines.␈α⊃ For␈α⊃example,␈α⊃streaming␈↓↓18␈↓␈α⊃intermediate␈α∩results␈α⊃of
compiler␈α∃passes␈α∃between␈α∃coroutines␈α∃circumvents␈α∃expensive
temporary␈α storage␈α allocation␈α and␈α speeds␈α up␈α the␈α compiler.
␈↓ α↑␈↓
Conclusions␈↓
␈↓ Some␈α∪of␈α∀the␈α∪design␈α∪decisions␈α∀of␈α∪LISP70␈α∪are␈α∀contrary␈α∪to
trends␈α
seen␈α
in␈α∞other␈α
"successors␈α
to␈α∞LISP".␈α
The␈α
goals␈α∞of␈α
these
languages␈α are␈α similar,␈α but␈α their␈α means␈α are␈α often␈α quite␈α diverse.
Concern␈α⊂with␈α⊃good␈α⊂notation␈α⊂does␈α⊃not␈α⊂have␈α⊃to␈α⊂compromise
the␈α⊃development␈α⊃of␈α⊃powerful␈α⊃facilities;␈α⊃indeed,␈α∩good␈α⊃notation
can␈α
make␈α
those␈α
facilities␈α
more␈α
convenient␈α
to␈α
use.␈α
People␈α who
"think␈α
in␈α
Algol"␈α
should␈α
not␈α
have␈α
to␈α
cope␈α
with␈α
S-expressions␈α to
write␈α∨algorithms.␈α∨ Neither␈α∨should␈α∨people␈α∨who␈α "think␈α∨in
patterns".␈α⊃ Rewrites,␈α⊃MLISP,␈α⊃and␈α∩LISP␈α⊃can␈α⊃be␈α⊃mixed,␈α∩and␈α⊃the
most␈α∩appropriate␈α∪means␈α∩of␈α∩defining␈α∪a␈α∩given␈α∩function␈α∪can␈α∩be
selected.
LISP70␈α
does␈α
not␈α
limit␈α
the␈α
use␈α
of␈α
pattern␈α
rewrite␈α
rules␈α
to␈α
a
few␈α
facilities␈α
like␈α
goal-achievement␈α
and␈α∞assertion-retrieval.␈α
A
set␈α↔of␈α↔rules␈α↔can␈α_be␈α↔applied␈α↔to␈α↔arguments␈α↔like␈α_any␈α↔other
function,␈α⊃and␈α⊃can␈α⊃stream␈α⊃data␈α⊃from␈α⊃any␈α⊃type␈α⊃of␈α∩structure␈α⊃or
process␈α to␈α any␈α other.
Automatic␈α∞ordering␈α∞does␈α∂not␈α∞prevent␈α∞the␈α∂programmer␈α∞from
seizing␈α_control,␈α→but␈α_allows␈α_him␈α→to␈α_relinquish␈α_control␈α→to␈α_a
procedure␈α∪of␈α∀his␈α∪choosing␈α∀to␈α∪save␈α∪him␈α∀tedious␈α∪study␈α∀of␈α∪an
existing␈α program␈α when␈α making␈α extensions.
Preliminary␈α
versions␈α
of␈α LISP70␈α
have␈α
been␈α run␈α
on␈α
a␈α PDP-10
using␈α↔a␈α↔bootstrap␈α⊗compiler.␈α↔ As␈α↔of␈α⊗June␈α↔15,␈α↔a␈α⊗production
version␈α
has␈α∞not␈α
been␈α
completed.␈α∞ The␈α
language␈α
has␈α∞been␈α
used
successfully␈α⊂in␈α⊂programs␈α⊂for␈α⊂question-answering␈α⊂and␈α∂planning.
Extensions␈α≠are␈α≠planned␈α~to␈α≠improve␈α≠its␈α≠control␈α~structure,
editing,␈α≤and␈α≤debugging␈α≥capabilities,␈α≤and␈α≤versions␈α≥will␈α≤be
bootstrapped␈α to␈α other␈α computers.
␈↓␈↓ α(␈↓
Acknowledgment␈↓
␈↓ The␈α authors␈α wish␈α to␈α thank␈α Alan␈α Kay␈α for␈α valuable␈α insights.
␈↓π␈↓ α⎇␈↓λREFERENCES␈↓π
␈↓↓1␈↓π Abrahams,␈α∃P.␈α∃W.␈α∃et␈α∃al,␈α∃"The␈α∃LISP␈α∃2␈α∃Programming␈α⊗Language␈α∃and
System",␈α
␈↓λProc.␈α
AFIPS␈α
FJCC␈α
29␈↓π␈α
(1966),␈α
661-676
␈↓↓2␈↓π Bobrow,␈α D.␈α G.␈α and␈α Wegbreit,␈α B.,␈α "A␈α Model␈α and␈α Stack␈α Implementation␈α of
Multiple␈α≤Environments",␈α≤Report␈α≠No.␈α≤2334␈α≤(March 1972),␈α≠Bolt,
Beranek,␈α
and␈α
Newman
␈↓↓3␈↓π Bobrow,␈α D.␈α G.,␈α "Requirements␈α for␈α Advanced␈α Programming␈α
Systems␈α for
List␈α
Processing",␈α
␈↓λComm. ACM␈α
15␈↓π,␈α
7␈α
(July 1972),␈α
618-627
␈↓↓4␈↓π Brown,␈α P.␈α J.,␈α "Levels␈α of␈α Language␈α for␈α Portable␈α
Software",␈α ␈↓λComm. ACM
15␈↓π,␈α
12␈α
(Dec. 1972),␈α
1059-1062
␈↓↓5␈↓π Burstall,␈α R.M.,␈α Collins,␈α J.S.␈α and␈α Popplestone,␈α R.J.,␈α ␈↓λProgramming␈α in␈α
Pop-2␈↓π,
University␈α
Press,␈α
Edinburg,␈α
Scotland␈α
(1971),␈α
279-282
␈↓↓6␈↓π Colby,␈α≠K.␈α≤M.␈α≠and␈α≠Enea,␈α≤H.,␈α≠"Heuristic␈α≠Methods␈α≤for␈α≠Computer
Understanding␈α⊂of␈α⊂Natural␈α⊂Language␈α⊂in␈α⊂Context␈α⊃Restricted␈α⊂On-Line
Dialogues",␈α
␈↓λMath.␈α
Biosciences␈α
1␈↓π␈α
(1967),␈α
1-25
␈↓↓7␈↓π Colby,␈α∪K.␈α∪M.,␈α∩Watt,␈α∪J.,␈α∪and␈α∩Gilbert,␈α∪J.␈α∪P.,␈α∩"A␈α∪Computer␈α∪Method␈α∩of
Psychotherapy",␈α ␈↓λJ.␈α
of␈α Nervous␈α
and␈α Mental␈α
Disease␈α 142␈↓π␈α
(1966),␈α 148-
152
␈↓↓8␈↓π Dickman,␈α∪B.␈α∪N.,␈α∪"ETC:␈α∪An␈α∪Extensible␈α∪Macro␈α∪Based␈α∪Compiler",␈α∩␈↓λProc.
AFIPS␈α
SJCC␈α
38␈↓π␈α
(1971),␈α
529-538
␈↓↓9␈↓π Duby,␈α
J.␈α
J.,␈α
"Extensible␈α
Languages:␈α
A␈α
Potential␈α
User's␈α
Point␈α
of␈α View",␈α
in
[21],␈α∧pp.137-140
␈↓↓10␈↓π Enea,␈α
H.,␈α
Colby,␈α
K.␈α
M.,␈α
and␈α
Moravec,␈α
H.,␈α
"Idiolectic␈α Language-Analysis
for␈α
Understanding␈α
Doctor-Patient␈α
Dialogues",␈α
(in␈α
this␈α
proceedings)
␈↓↓11␈↓π Enea,␈α≥H.,␈α≡and␈α≥Tesler,␈α≡L.,␈α≥"INTEGRATE",␈α≡Unpublished␈α≥Stanford
University␈α
Class␈α
Project␈α
(1964)
␈↓↓12␈↓π Enea,␈α∞H.,␈α∞"MLISP␈α∂(IBM␈α∞360/67)",␈α∞Computer␈α∞Science␈α∂Technical␈α∞Report
CS␈α
92␈α
(1968),␈α
Stanford␈α
University
␈↓↓13␈↓π Guzman,␈α∂A.,␈α∂and␈α∞McIntosh,␈α∂H.␈α∂V.,␈α∞"CONVERT",␈α∂␈↓λComm. ACM␈α∂9␈↓π,␈α∂8␈α∞(Aug.
1966),␈α
604-615
␈↓↓14␈↓π Hewitt,␈α C.,␈α ␈↓λPLANNER:␈α A␈α Language␈α for␈α Manipulating␈α Models␈α and␈α Proving
Theorems␈α
in␈α
a␈α
Robot␈↓π,␈α
Ph.D.␈α
Thesis␈α
(Feb␈α
1971),␈α
MIT
␈↓↓15␈↓π Hewitt,␈α∞C.,␈α∞"Procedural␈α∞Embedding␈α∞of␈α∞Knowledge␈α∞in␈α∂PLANNER",␈α∞␈↓λProc.
IJCAI␈α
2␈↓π␈α
(1971),␈α
167-182
␈↓↓16␈↓π Kay,␈α∩A.,␈α⊃"FLEX,␈α∩A␈α⊃Flexible␈α∩Extendible␈α⊃Language",␈α∩CS␈α∩Tech.␈α⊃Report
(1968),␈α
U.␈α
of␈α
Utah
␈↓↓17␈↓π Landin,␈α P.␈α J.,␈α "The␈α Next␈α 700␈α Programming␈α Languages",␈α ␈↓λComm.␈α ACM␈α 9␈↓π,
3␈α
(March 1966),␈α
157-166
␈↓↓18␈↓π Leavenworth,␈α B.␈α M.,␈α "Definition␈α of␈α Quasi-Parallel␈α Control␈α
Functions␈α in
a␈α
High-Level␈α
Language",␈α
␈↓λProc.␈α
Int'l.␈α
Comp.␈α
Symp.␈↓π␈α
(Bonn, 1970)
␈↓↓19␈↓π McCarthy,␈α J.,␈α "Recursive␈α Functions␈α of␈α Symbolic␈α Expressions␈α and␈α their
Computation␈α
by␈α Machine,␈α
Part␈α I",␈α
␈↓λComm. ACM␈α 3␈↓π,␈α
4␈α (April 1960),␈α
184-
195
␈↓↓20␈↓π Rulifson,␈α∞J.␈α
F.,␈α∞Waldinger,␈α
R.␈α∞J.,␈α
and␈α∞Derksen,␈α
J.␈α∞A.,␈α
␈↓λQA4,␈α∞A␈α
Language
for␈α Writing␈α Problem-Solving␈α
Programs␈↓π,␈α ␈↓λProc.␈α IFIP␈↓π␈α (1968),␈α
TA-2,␈α 111-
115
␈↓↓21␈↓π Schuman,␈α∩S.,␈α∩ed.,␈α∩"Proceedings␈α⊃of␈α∩the␈α∩International␈α∩Symposium␈α⊃on
Extensible␈α
Languages",␈α
␈↓λACM␈α
SIGPLAN␈α
Notices␈α
6␈↓π,␈α
12␈α
(Dec. 1971)
␈↓↓22␈↓π Smith,␈α
D.␈α
and␈α
Enea,␈α
H.,␈α
"Backtracking␈α
in␈α
MLISP2",␈α
(in␈α
this␈α
proceedings)
␈↓↓23␈↓π Smith,␈α∪D.,␈α∪"MLISP␈α∪(PDP-10)",␈α∪Artificial␈α∪Intelligence␈α∪Memo␈α∪No.␈α∪135,
Stanford␈α
University,␈α
Oct.␈α
1970
␈↓↓24␈↓π Smith,␈α D.C.␈α and␈α Enea,␈α H.J.,␈α ␈↓λMLISP2␈α Manual␈↓π,␈α Artificial␈α Intelligence␈α Memo
No.␈α
195,␈α
Stanford␈α
University,␈α
June␈α
1973
␈↓↓25␈↓π Sussman,␈α
G.␈α∞J.␈α
and␈α∞McDermott,␈α
D.␈α∞V.,␈α
"Why␈α∞Conniving␈α
is␈α∞Better␈α
than
Planning",␈α
␈↓λProc.␈α
AFIPS␈α
FJCC␈α
41␈↓π␈α
(1972),␈α
1171-1180
␈↓↓26␈↓π Teitelman,␈α⊃W.␈α⊃et␈α⊃al,␈α⊃␈↓λBBN-LISP␈α⊃Reference␈α⊃Manual␈↓π,␈α∩(July 1971),␈α⊃Bolt,
Beranek,␈α
and␈α
Newman
␈↓↓27␈↓π Teitelman,␈α∩W.,␈α∩"Toward␈α∩a␈α∩Programming␈α∩Laboratory",␈α∩␈↓λProc.␈α∩IJCAI␈α∩1␈↓π
␈↓π (1969),␈α
1-8
␈↓↓28␈↓π Teitelman,␈α∃W.,␈α∀␈↓λDesign␈α∃and␈α∀Implementation␈α∃of␈α∀FLIP,␈α∃a␈α∃LISP␈α∀Format
Directed␈α⊂List␈α∂Processor␈↓π,␈α⊂Scientific␈α∂Report␈α⊂No.␈α∂10␈α⊂(July 1967),␈α∂Bolt,
Beranek,␈α
and␈α
Newman
␈↓↓29␈↓π Wegbreit,␈α∂B.,␈α∞"The␈α∂ECL␈α∞Programming␈α∂System",␈α∞␈↓λProc.␈α∂AFIPS␈α∂FJCC␈α∞39␈↓π
(1971),␈α
253-262
␈↓↓30␈↓π Weizenbaum,␈α∩J.,␈α⊃"ELIZA␈α∩--␈α⊃A␈α∩computer␈α⊃Program␈α∩for␈α⊃the␈α∩Study␈α⊃of
Natural␈α Communication␈α Between␈α Man␈α and␈α Machine",␈α ␈↓λComm.␈α ACM␈α 9␈↓π,␈α 1
(Jan. 1966),␈α
36-45",